package com.Sep_Nine;


import java.util.ArrayList;
import java.util.List;

/**
 * 113. 路径总和 II
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/path-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution113 {
    List<List<Integer>> res=new ArrayList<>();

    public List<List<Integer>> pathSum(Solution112.TreeNode root, int targetSum) {
        backTrac(root,targetSum,new ArrayList<>());
        return res;
    }

    public void backTrac(Solution112.TreeNode root, int targetSum, List<Integer> tmp){
        if (root==null) return;
        tmp.add(root.val);
        if (root.left==null&&root.right==null)
        {
            if (targetSum-root.val==0)
            {
                res.add(tmp);
            }
        }
        backTrac(root.left,targetSum-root.val,tmp);
        backTrac(root.right,targetSum-root.val,tmp);
        tmp.remove(tmp.size()-1);
    }
}
